package com.likou;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class q94 {

    public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        List<Integer> list = new ArrayList<>();

        while (root != null || !deque.isEmpty()) {
            while (root != null) {
                deque.push(root);
                root = root.left;
            }

            TreeNode pop = deque.pop();
            list.add(pop.val);
            root = pop.right;
        }

        return list;
    }

//    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> list = new ArrayList<>();
//        inorder(root, list);
//
//        return list;
//    }
//
//    private void inorder(TreeNode root, List<Integer> list) {
//        if (root == null) {
//            return;
//        }
//        inorder(root.left, list);
//        list.add(root.val);
//        inorder(root.right, list);
//    }
}
